#ifndef VL_GENERIC_HASH_SET
#define VL_GENERIC_HASH_SET

#include <cstddef>
#include <vector>
#include <utility>
#include <functional>
#include "debug.hpp"

namespace vl
{

/*
Generic hash set

generic_hash_set<T, KeyT, Hash, Compare>

Let t : generic_hash_set<T, KeyT, Hash, Compare>
    a, b : T
    
Requirements:

Hash is a function of type (KeyT -> integer in 0..MaxInt).
Compare is a transitive, reflexive, symmetrical, binary relation on KeyT.

T::key : T -> KeyT
T::is_empty : T -> Boolean
T::is_filled : T -> Boolean
T::make_empty : T -> Void
T::make_deleted : T -> Void
T::assign_value : T T -> Void
T::value : T -> ValueT

a.is_empty() iff 'a' does not have a key, nor value.
a.is_filled() iff 'a' does have a key and/or value.
(T()).is_empty() == true
a.is_empty() => !a.is_filled()
a.is_filled() => !a.is_empty()

a.assign_value(b) assigns the value part of 'b' to 'a' (if any). A precondition
	is that Compare(a.key(), b.key()) == true, so the function can assign
	the key part as well without breaking the semantics.
	
a.make_empty():
	Precond:   a.is_filled() && !a.is_empty()
	Postcond: !a.is_filled() &&  a.is_empty()
	
a.make_deleted():
	Precond:   a.is_filled() && !a.is_empty()
	Postcond: !a.is_filled() && !a.is_empty()

Compare(a.key(), b.key()) == true iff the keys of 'a' and 'b' are equal

Compare(a.key(), b.key()) == true => Hash(a.key()) == Hash(b.key())

If SafeEmptyKey == true, then // NOTE: This is not made use of
	a.is_empty() && !b.is_empty() => Compare(a.key(), b.key()) == false



Operations:


*/

/*
inline std::size_t second_hash(std::size_t h)
{
	return (h * 2654435769ul) ^ (h >> 16); // TODO: Adjust this
}
*/

std::size_t next_prime(std::size_t n);
std::size_t prev_prime(std::size_t n);

template<int ID, typename BaseT>
struct base_select : BaseT
{
	base_select(BaseT const& b)
	: BaseT(b) {}
};

inline std::size_t hash(int v)
{
	return std::size_t(v);
}

inline std::size_t hash(std::size_t v)
{
	return v * 2654435761ul ^ (v >> 16);
}

template<typename T1, typename T2>
inline std::size_t hash(std::pair<T1, T2> const& v)
{
	return (hash(v.first) * 2654435761ul) ^ hash(v.second);
}

template<typename T>
inline std::size_t hash(T const& v)
{
	return v.hash();
}

struct hash_functor
{
	template<typename T>
	std::size_t operator()(T const& v) const
	{
		return hash(v);
	}
};

template<typename T>
inline T* dummy_ptr()
{
	return reinterpret_cast<T*>(1);
}

template<typename T>
inline bool is_null_or_dummy_ptr(T* p)
{
	return p <= dummy_ptr<T>(); // Assumes dummy_ptr is 1
}

template<typename T, typename KeyT, typename ValueT, typename Hash = hash_functor, typename Compare = std::equal_to<KeyT>, bool SafeEmptyKey = false>
struct generic_hash_set : Hash, Compare
{
	typedef Compare compare_type;
	
	// NOTE: Compare can't be the same type as Hash. This is a (minor) semantics issue.
	
	//typedef T index_type;
	
	/*
	struct iterator
	{
		iterator(T* p)
		: p(p)
		{
		}
		
		ValueT& operator*()
		{
			return p->value();
		}
		
		iterator& operator++()
		{
			++p;
			return *this;
		}
		
		T* p;
	};*/
	
	generic_hash_set(
		Hash const& hash = Hash(),
		Compare const& compare = Compare())
	: Hash(hash), Compare(compare)
	, t(11), tsize(11)
	, elems(0)
	, deleted(0)
	, uload(0.666)
	, lload(0.20)
	, shload(0.45) // 2*lload < shload < uload
	{
	}
	
	~generic_hash_set()
	{
		clear();
	}
	
	void clear()
	{
		for(std::size_t i = 0; i < tsize; ++i)
		{
			if(t[i].is_filled())
				t[i].make_empty();
			else if(!t[i].is_empty())
				t[i] = T();
		}
		elems = 0;
	}
	
	template<typename SpecKeyT>
	T* lookup(SpecKeyT const& k)
	{
		std::size_t h = Hash::operator()(k);
		
		int step = 1;
		do
		{
			T& slot = t[h % tsize];
			
			if(slot.is_empty())
				return 0;
			if(slot.is_filled() && Compare::operator()(slot.key(), k))
				return &slot;
			
			h += step; step += 2;
		}
		while(step < 64);
		
		return 0;
	}
	
	bool try_insert(T const& v)
	{
		std::size_t h = Hash::operator()(v.key());
		
		std::size_t step = 1;
		do
		{
			T& slot = t[h % tsize];
			
			if(!slot.is_filled())
			{
				if(!slot.is_empty())
					--deleted;
				++elems;
				slot = v;
				ASSERT(slot.is_filled());
				return true;
			}

			h += step; step += 2;
		}
		while(step < 64);
		
		return false;
	}
	
#if 0 // WRONG!
	void try_insert_check_unique(T const& v)
	{
		while(true)
		{
			std::size_t h = Hash::operator()(v.key());
			
			std::size_t step = 1;
			do
			{
				T& slot = t[h % tsize];
				
				if(!slot.is_filled())
				{
					if(!slot.is_empty())
						--deleted;
					++elems;
					slot = v;
					ASSERT(slot.is_filled());
					return;
				}
				else if(Compare::operator()(slot.key(), v.key()))
				{
					slot.assign_value(v);
					return;
				}

				h += step; step += 2;
			}
			while(step < 64);
			
			enlarge();
		}
	}
#endif
	
	void insert(T const& v)
	{
		maybe_enlarge();
		
		T* idx = lookup(v.key());
		if(idx)
			idx->assign_value(v);
		else
			try_insert(v);
	}
		
	template<typename SpecKeyT>
	void remove(SpecKeyT const& k)
	{
		T* idx = lookup(k);
		
		if(idx)
		{
			ASSERT(idx->is_filled());
			idx->make_deleted();
			ASSERT(!idx->is_filled());
			--elems;
			++deleted;
			maybe_shrink();
		}
	}
	
	template<typename Pred>
	void erase_if(Pred pred = Pred())
	{
		for(std::size_t i = 0; i < t.size(); ++i)
		{
			if(t[i].is_filled()
			&& pred(t[i].value()))
			{
				t[i].make_deleted();
				--elems;
				++deleted;
			}
		}
		
		maybe_shrink();
	}
	
	std::size_t size() const
	{
		return elems;
	}
	
protected:
	void rehash(std::vector<T>& e)
	{
		deleted = 0; // There will be no deleted elements afterwards
try_insert:
		elems = 0;
		for(std::size_t i = 0; i < e.size(); ++i)
		{
			if(e[i].is_filled()
			&& !try_insert(e[i]))
			{
				// We need to make the table larger

				tsize = next_prime(tsize + 1);
				
				t.assign(tsize, T());

				goto try_insert;
			}
		}
	}
	
	void maybe_enlarge()
	{
		if(elems >= std::size_t(tsize * uload))
		{
			enlarge();
		}
	}
	
	void maybe_shrink()
	{
		if(elems <= std::size_t(tsize * lload)
		&& tsize > 11)
		{
			shrink();
		}
	}
	
	void enlarge()
	{
		tsize = next_prime(tsize + 1);
		
		std::vector<T> temp(tsize);
		
		t.swap(temp);

		// temp is now the old vector, reinsert all the old elements
		
		rehash(temp);
	}
	
	void shrink()
	{
		tsize = next_prime(std::size_t(elems / shload));
		
		std::vector<T> temp(tsize);
		
		t.swap(temp);

		// temp is now the old vector, reinsert all the old elements
		
		rehash(temp);
	}
	
	std::size_t tsize;
	std::vector<T> t;
	std::size_t elems;
	std::size_t deleted; // NOTE: Do we need to keep track of this?
	
	double uload; // Load limit where size is increased
	double lload; // Load limit where size is decreased
	double shload; // Approximate load after shrinking
};

}

#endif // VL_GENERIC_HASH_SET
